1 Contenido de la clase
El problema de selección: conocer la posición de un elemento [08:21-08:25]
Se parte de la idea de tomar un elemento y ver cuál es su posición en la lista. Con índices de 1 a 16, la posición indica cuántos elementos quedan antes y cuántos después. La mediana es el elemento que queda en la posición central, con la misma cantidad de elementos más chicos que más grandes [08:49-08:51].
Contar más chicos y más grandes para ubicar un elemento [09:41-22:14]
Para saber en qué posición está un elemento hay que contar cuántos son más chicos y cuántos son más grandes que él. Con el 11, "10 más chicos y 5 más grandes" [09:41-09:57]; "mayores que 11 son 5, menores 10" [21:06-22:14]. También se muestra el ejemplo con el 3: "más grandes que 3 hay tres" [20:32-20:42]. La forma directa es recorrer toda la lista contando, lo que por sí solo cuesta un recorrido completo.
Partir la lista en grupos de 5 [22:36-29:14]
Como los números están desordenados, se propone partir la lista en grupos de 5: "aquí tengo múltiplos de 5, tomamos los primeros 5, los segundos 5, los últimos 5" [22:36-22:54]. Cada grupo de 5 se ordena; ordenar 5 elementos cuesta 7 comparaciones [27:39-29:14]. Con 15 elementos quedan 3 listas de 5 [28:02-28:08].
La mediana de cada grupo y la mediana de las medianas [24:18-24:27, 43:56-46:15]
De cada grupo ordenado se toma su mediana [24:18-24:27]. Luego se toma la mediana de las medianas, que se usa como pivote [43:56-44:01, 46:03-46:15]. En un ejemplo con 20 elementos (4 grupos de 5), el costo de ordenar todos los grupos es 7 · (n/5) comparaciones [43:18-44:19]. Se compara cada mediana con el pivote: "el 10 con el 8" queda más grande y "el 7 con el 8 queda más chico" [43:58-44:19].
Particionar y descartar [44:25-48:16]
Con el pivote se particiona la lista en dos grupos: los chicos (menores que el pivote) y los grandes (mayores o iguales) [44:25-44:46]. Como se conoce la posición del pivote, se pueden descartar los elementos que no pueden contener a la respuesta: "elimina estos dos valores" [42:39-42:45], "puedo descartar quiénes" [40:00-40:27]. Se cuenta cuántos elementos quedan de cada lado y se repite recursivamente sobre el lado que contiene al elemento buscado [45:41-48:16].
La recurrencia y el análisis de linealidad [48:56-62:52]
Se analiza el costo total. Hay n/5 grupos y cada uno cuesta 7 comparaciones [49:16-49:20, 62:33-62:40]. Tras el descarte queda menos de 7n/10 elementos [48:56-49:56, 60:10-62:52]. La recurrencia queda:
T(n) ≤ T(n/5) + T(7n/10) + O(n)
Al repetir el proceso, la suma de los términos converge a una función lineal: el costo total es O(n) [60:10-62:52]. Así se consigue seleccionar el k-ésimo elemento en tiempo lineal en el peor caso, sin ordenar la lista completa.
Discusión final de la implementación [63:46-64:54]
La parte final de la clase discute detalles de la implementación del algoritmo y se confirma el valor del pivote elegido [63:46-64:54]. [parte no entendida — detalle final del desarrollo en la pizarra].
2 Puntos destacados / Lo que hay que saber
3 Actividades y tareas pendientes
En esta clase no se dejó ninguna tarea concreta con fecha de entrega. Conviene practicar por cuenta propia:
4 Dudas que podrían examinar
¿Qué es el problema de selección?
Encontrar el k-ésimo elemento más pequeño de una lista (la mediana es el caso central), sin necesidad de ordenar toda la lista [08:21-08:25].
¿Por qué ordenar cada grupo de 5 cuesta 7 comparaciones?
Porque ordenar 5 elementos exige hasta 7 comparaciones (log₂(5!) ≈ 6.9) [27:39-29:14].
¿Por qué se usa la mediana de las medianas como pivote?
Porque garantiza que el pivote quede "en el medio" y permite descartar siempre una fracción fija de elementos, evitando el caso peor de la selección rápida [43:56-46:15].
¿Cuántos elementos se descartan en cada paso?
Al menos 3n/10; tras el descarte quedan a lo más 7n/10 [48:56-49:56].
¿Por qué el algoritmo es O(n) y no O(n log n)?
Porque la recurrencia T(n) ≤ T(n/5) + T(7n/10) + O(n) tiene solución lineal [60:10-62:52].
¿Seleccionar es más barato que ordenar?
Sí: seleccionar el k-ésimo cuesta O(n), mientras que ordenar toda la lista cuesta O(n log n).
5 Sitios o recursos para visitar
El profesor no citó libros, páginas ni herramientas concretas en esta clase. Recursos útiles para profundizar lo explicado:
El algoritmo de selección lineal determinística con grupos de 5. · google.com
Nombre clásico del algoritmo (Blum, Floyd, Pratt, Rivest, Tarjan, 1973). · google.com
Selección del k-ésimo elemento más pequeño con la mediana de las medianas. · geeksforgeeks.org
Curso completo de introducción a algoritmos. · ocw.mit.edu
Capítulo de selección del libro de referencia clásico. · google.com
Visualizaciones interactivas de algoritmos de ordenación y selección. · visualgo.net
6 Glosario de términos
- Selección: problema de encontrar el k-ésimo elemento más pequeño de una lista (la mediana es el caso central).
- Mediana: elemento que deja la misma cantidad de elementos más chicos que más grandes.
- Pivote: elemento elegido para particionar la lista en dos grupos.
- Mediana de las medianas: la mediana de las medianas de los grupos de 5; pivote determinístico del algoritmo.
- Particionar: dividir la lista en chicos (menores que el pivote) y grandes (mayores o iguales).
- Descartar: eliminar del análisis los elementos que no pueden contener a la respuesta buscada.
- Recurrencia: ecuación que expresa el costo de un algoritmo recursivo en función de sí mismo.
- Algoritmo lineal (O(n)): algoritmo cuyo tiempo crece proporcionalmente al tamaño de la entrada.
- Comparación: operación básica de orden entre dos elementos; ordenar 5 elementos cuesta 7 comparaciones.
7 Mapa mental textual
- Diseño y Análisis de Algoritmos · Clase 6
- Problema de selección
- Encontrar el k-ésimo elemento más pequeño (la mediana)
- Ubicar un elemento contando más chicos y más grandes
- No hace falta ordenar toda la lista
- Mediana de las medianas
- Partir en grupos de 5 (múltiplos de 5)
- Ordenar cada grupo: 7 comparaciones
- Tomar la mediana de cada grupo
- La mediana de las medianas es el pivote
- Particionar y descartar
- Chicos (< pivote) y grandes (≥ pivote)
- Se descartan los elementos que no pueden ser la respuesta
- Quedan a lo más 7n/10 elementos
- Análisis de la recurrencia
- T(n) ≤ T(n/5) + T(7n/10) + O(n)
- El costo total es O(n)
- Selección lineal en el peor caso (vs. O(n log n) de ordenar)
- Problema de selección